# 
# Created by francklinson on 2021/7/31 AT 21:43.
#

# 统计所有小于非负整数 n 的质数的数量。


class Solution:
    def countPrimes(self, n: int) -> int:
        ans = 0
        for i in range(n):
            if self.isPrime(i):
                ans += 1
        return ans

    def isPrime(self, n):
        """
        n是否质数  2到根号n
        :param n:
        :return:
        """
        if n <= 1:
            return False
        i = 2
        while i * i <= n:
            if n % i == 0:
                return False
            i += 1
        return True


class Solution2:
    def countPrimes(self, n: int) -> int:
        # 埃式筛
        isPrime = [1 for _ in range(n)]
        ans = 0
        for i in range(2, n, 1):
            if isPrime[i] == 1:
                ans += 1
                if i * i < n:
                    # 质数的倍数都是非质数
                    for j in range(i * i, n, i):
                        isPrime[j] = 0
        return ans


if __name__ == '__main__':
    sol = Solution2()
    print(sol.countPrimes(10))
    print(sol.countPrimes(0))
    print(sol.countPrimes(1))
    print(sol.countPrimes(1500000))
